/**
 * @param {number} n
 * @return {number}
 */
 var numSquares = function(n) {
    let dp=new Array(n+1).fill(Infinity);
    let i=1;
    while(i*i<=n){
        dp[i*i]=1;
        i++;
    }
    for(i=1;i<n+1;i++){
        for(let j=1;j<=i/2;j++){
            dp[i]=Math.min(dp[i],dp[j]+dp[i-j]);
        }
    }
    return dp[n];
};


// 执行用时：
// 1784 ms
// , 在所有 JavaScript 提交中击败了
// 5.12%
// 的用户
// 内存消耗：
// 41.4 MB
// , 在所有 JavaScript 提交中击败了
// 80.26%
// 的用户


var numSquares = function(n) {
    let dp=new Array(n+1).fill(Infinity);
    let i=1;
    while(i*i<=n){
        dp[i*i]=1;
        i++;
    }
    if(dp[n]==1){
        return 1
    }
    for(i=1;i<n+1;i++){
        if(dp[i]!=1){
            for(let j=1;j*j<=i;j++){
                dp[i]=Math.min(dp[i],dp[j*j]+dp[i-j*j]);
            }
        }
    }
    return dp[n];
};

// 执行用时：
// 232 ms
// , 在所有 JavaScript 提交中击败了
// 57.16%
// 的用户
// 内存消耗：
// 41.2 MB
// , 在所有 JavaScript 提交中击败了
// 90.94%
// 的用户



console.log(numSquares(9999))